package Hard;

//41.缺失的第一个正数
//要求使用O(N)的时间复杂度和O(1)的空间复杂度
//别看了，下面都是错的
public class Solution41 {
    public static int firstMissingPositive(int[] nums) {
        //非负个数
        int count = nums.length;
        //去掉负数和0
        for (int i = 0; i < count; i++) {
            if (nums[i] < 1) {
                nums[i] = nums[count - 1];
                i--;
                count--;
            }
        }
        boolean minIsOneValid = false;
        boolean postCountIsDcount = false;
        int min = Integer.MAX_VALUE;
        int lastMin = min;
        int lastMinIndex = -1;
        int minIndex = -1;
        int postCount = count - 1;
        int t = 0;//pC
        for (int i = 0; i < count; i++, postCount--) {
            if (nums[i] == 1) {
                //说明1这个数出现过了
                minIsOneValid = true;
            }
            if (nums[i] == Integer.MAX_VALUE || nums[i] + 1 == min) {
                //遇到比自己刚好小1的数，则最小数还是自己
                continue;
            }
            if (nums[i] == min + 1) {
                //遇到刚好比自己大1的数，则最小数变为此数
                min = nums[i];
                continue;
            }
            if (nums[i] < min) {
                //当前数至少比最小数小2的情况
                lastMin = min;
                lastMinIndex = minIndex;
                min = nums[i];
                minIndex = i;
                t = 0;
                if (postCount != 0 && postCount + 1 == min) {
                    postCountIsDcount = true;
                }
            } else if (nums[i] > min) {
                postCountIsDcount = false;
                //[9,3,1,2,6,4]
                if (lastMin + (++t) == count - lastMinIndex)
                    postCountIsDcount = true;
            }
        }
        if (minIsOneValid && (!postCountIsDcount) )
            return min + 1;
        else if (postCountIsDcount) {
            return lastMin + 1;
        } else
            return 1;
    }

    public static void main(String[] args) {
        System.out.println(firstMissingPositive(new int[]{2,3, 4, 1}));
    }
}
